package com.coder.algorithm.leetcode

/**
 * [151. 颠倒字符串中的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/)
 * [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/)
 *
 * @author yuhus
 * @date: 2022/3/16
 */
class l_0151 {
    fun reverseWords(s: String): String {
        if (s.isEmpty()) {
            return s
        }
        val charArray = s.toCharArray()
        // 1. 去空格
        var len = 0
        charArray.forEach {
            if (it == ' ') {
                // 非前导空格，多空格
                if (len > 0 && charArray[len - 1] != ' ') {
                    charArray[len++] = it
                }
            } else {
                charArray[len++] = it
            }
        }
        if (charArray[len - 1] == ' ') {
            len--
        }
        // 2. 全部翻转
        reverseWords(charArray, 0, len - 1)
        // 3-1. 翻转单词（排除最后一个）
        var start = 0
        for (index in 0 until len) {
            if (charArray[index] == ' ') {
                reverseWords(charArray, start, index - 1)
                start = index + 1
            }
        }
        // 3-2. 翻转单词（最后一个）
        reverseWords(charArray, start, len - 1)
        return String(charArray, 0, len)
    }

    private fun reverseWords(charArray: CharArray, l: Int, r: Int) {
        var start = l
        var end = r
        var temp: Char
        while (start < end) {
            temp = charArray[start]
            charArray[start] = charArray[end]
            charArray[end] = temp
            start++
            end--
        }
    }

    fun reverseWords_solution1(s: String): String {
        var result = ""
        s.split(" ").filter { it.isNotEmpty() }.reversed().forEach {
            result += "$it "
        }
        if (result.endsWith(" ")) {
            result = result.substring(0, result.length - 1)
        }
        return result
    }


}